/**
 * Copyright (c) 2012 Nokia Corporation.
 */

package com.nokia.example.tictactoe.engine;

/**
 * AI opponent which intelligence is based on a simple Minimax algorithm.
 */
public class MinimaxAI implements ITicTacToeAI {
	// Constants
	private static final int UNDEFINED = -1;
	private static final int MIN = -9999;
	
	// Members
	private int _depth = 1;
	private int _gridSizeSquared = 0;
	private int _marksRequiredToWin = 0;
	private int _bestValue = MIN;
	private int _deepest = 0;
	private boolean _bestFound = false;
	
	/**
	 * Constructor.
	 * @param depth The maximum depth for recursion. Note that increasing the
	 * 				depth also increases the complexity of the AI exponentially.
	 */
	public MinimaxAI(int depth) {
		if (depth > 0) {
			_depth = depth;
		}
	}
	
	/**
	 * From ITicTacToeAI.
	 */
	public int[] nextMove(GameModel model, int aiMark) {
		int[] markXY = new int[2];
		markXY[0] = markXY[1] = UNDEFINED;
		_gridSizeSquared = model.gridSizeSquared();
		_marksRequiredToWin = model.marksRequiredToWin();
		_bestValue = MIN;
		_deepest = 0;
		_bestFound = false;
		minimax(model.grid(), aiMark, markXY, 0);
		return markXY;
	}
	
	/**
	 * The recursive algorithm for establishing the next "best" move.
	 * @param grid The game grid.
	 * @param aiMark The mark of the AI.
	 * @param bestXY Where the coordinates of the next move are stored.
	 * @param depth The current depth in the recursion.
	 */
	private void minimax(int[] grid,
						 int aiMark,
						 int[] bestXY,
						 int depth)
	{
		int evaluation = 0;
		int temp = MIN;
		final int markToSet = (depth % 2 == 0) ? aiMark
				: (aiMark == GameModel.MARK_X) ? GameModel.MARK_O
						: GameModel.MARK_X; 
		
		for (int x = 0; x < _gridSizeSquared; ++x) {
			for (int y = 0; y < _gridSizeSquared; ++y) {
				if (setMark(grid, x, y, markToSet)) {
					evaluation = evaluateGrid(grid, aiMark);
					// Uncomment the following line for debugging:
					//printValue(depth, x, y, evaluation);
					
					if (temp == MIN) {
						temp = evaluation;
					}
					else {
						temp += evaluation;
					}
					
					if (depth + 1 <= _depth) {
						minimax(grid, aiMark, bestXY, depth + 1);
					}
					
					if (depth == 0 && _bestFound) {
						bestXY[0] = x;
						bestXY[1] = y;
						_bestFound = false;
					}
					
					// Undo the changes
					setMark(grid, x, y, GameModel.MARK_EMPTY);
				}
			}
		}
		
		if (depth > _deepest
				|| (depth == _deepest && temp > _bestValue))
		{
			_bestValue = temp;
			_deepest = depth;
			_bestFound = true;
			System.out.println("Found best value so far: "
					+ _bestValue + " @ " + _deepest);
		}
	}
	
	/**
	 * Evaluates the game state from the perspective of the given player.
	 * This method contains the main logic that can either make the AI dumb or
	 * smart. The default implementation is just dumb enough so that winning
	 * is possible.
	 * 
	 * @param grid The game grid containing the game state.
	 * @param fromPerspective From whose perspective to evaluate.
	 * @return The evaluation. The greater the better for the player.
	 */
	private int evaluateGrid(int[] grid, int fromPerspective) {
		int XCount = 0;
		int OCount = 0;
		int totalX = 0;
		int totalO = 0;
		int tempMark = GameModel.MARK_EMPTY;
		
		// Horizontal lines 
		for (int y = 0; y < _gridSizeSquared; ++y) {
			for (int x = 0; x < _gridSizeSquared; ++x) {
				tempMark = grid[y * _gridSizeSquared + x];
				
				if (tempMark == GameModel.MARK_X) {
					if (OCount > 0) {
						OCount = 0;
					}

					XCount++;
					totalX += XCount * XCount;
				}
				else if (tempMark == GameModel.MARK_O) {
					if (XCount > 0) {
						XCount = 0;
					}

					OCount++;
					totalO += OCount * OCount;
				}
				else {
					// Empty
					XCount = 0;
					OCount = 0;
				}

			}
			
			XCount = 0;
			OCount = 0;
		}
		
		// Vertical lines 
		for (int x = 0; x < _gridSizeSquared; ++x) {
			for (int y = 0; y < _gridSizeSquared; ++y) {
				tempMark = grid[y * _gridSizeSquared + x];
				
				if (tempMark == GameModel.MARK_X) {
					if (OCount > 0) {
						OCount = 0;
					}
					
					XCount++;
					totalX += XCount * XCount;
				}
				else if (tempMark == GameModel.MARK_O) {
					if (XCount > 0) {
						XCount = 0;
					}
					
					OCount++;
					totalO += OCount * OCount;
				}
				else {
					// Empty
					XCount = 0;
					OCount = 0;
				}
			}
			
			XCount = 0;
			OCount = 0;
		}
		
		// Diagonal, top-left to bottom-right
		int tempX = _gridSizeSquared - _marksRequiredToWin;
		int tempY = 0;
		
		if (tempX < 0) {
			// The game cannot be won!!!
			return MIN;
		}
		
		int x;
		int y;

		while (tempY <= _gridSizeSquared - _marksRequiredToWin) {
			x = tempX;
			y = tempY;
			
			while (x < _gridSizeSquared && y < _gridSizeSquared) {
				tempMark = grid[y * _gridSizeSquared + x];
				
				if (tempMark == GameModel.MARK_X) {
					if (OCount > 0) {
						OCount = 0;
					}
					
					XCount++;
					totalX += XCount * XCount;
				}
				else if (tempMark == GameModel.MARK_O) {
					if (XCount > 0) {
						XCount = 0;
					}
					
					OCount++;
					totalO += OCount * OCount;
				}
				else {
					// Empty
					XCount = 0;
					OCount = 0;
				}
				
				x++;
				y++;				
			}
			
			XCount = 0;
			OCount = 0;
			
			if (tempX > 0) {
				tempX--;
			}
			else {
				tempY++;
			}
		}
		
		tempX = _gridSizeSquared - 1;
		tempY = _gridSizeSquared - _marksRequiredToWin;
		
		// Diagonal, top-right to bottom-left
		while (tempX >= _marksRequiredToWin - 1) {
			x = tempX;
			y = tempY;
			
			while (x >= 0 && y < _gridSizeSquared) {
				tempMark = grid[y * _gridSizeSquared + x];
				
				if (tempMark == GameModel.MARK_X) {
					if (OCount > 0) {
						OCount = 0;
					}

					XCount++;
					totalX += XCount * XCount;
				}
				else if (tempMark == GameModel.MARK_O) {
					if (XCount > 0) {
						XCount = 0;
					}
					
					OCount++;
					totalO += OCount * OCount;
				}
				else {
					// Empty
					XCount = 0;
					OCount = 0;
				}
				
				x--;
				y++;
			}
			
			XCount = 0;
			OCount = 0;
			
			if (tempY > 0) {
				tempY--;
			}
			else {
				tempX--;
			}
		}
		
		if (fromPerspective == GameModel.MARK_X) {
			return totalX - totalO;
		}
		
		return totalO - totalX;
	}
	
	/**
	 * Sets the given mark in the given coordinates on the grid.
	 * @param grid The game grid
	 * @param x
	 * @param y
	 * @param mark
	 * @return True if was able to add the mark, false otherwise.
	 */
	private boolean setMark(int[] grid,
							final int x,
							final int y,
							final int mark)
	{
		final int index = y * _gridSizeSquared + x;
		
		if (mark != GameModel.MARK_EMPTY
				&& grid[index] != GameModel.MARK_EMPTY)
		{
			return false;
		}
		
		grid[index] = mark;
		return true;
	}
	
	/**
	 * Helper method for printing values of grid state evaluations.
	 * @param depth
	 * @param x
	 * @param y
	 * @param value
	 */
	private final void printValue(final int depth,
								  final int x,
								  final int y,
								  final int value)
	{
		for (int i = 0; i <= depth; ++i) {
			System.out.print(">");
		}
		System.out.println(" [" + (x + 1) + ", " + (y + 1) + "]: " + value);
	}
}
